# 动态规划50题 https://www.bilibili.com/video/BV1aa411f7uT
# 11/50 单词拆分
# leetcode第139题: https://leetcode.cn/problems/word-break/description/
# Date: 2024/10/31
def wordBreak(s: str, wordDict: list[str]) -> bool:
    """我的解法, 主要参考了dp10, 相比与优化的算法, 运算时间稍高"""
    n = len(s)
    dp = [False] * (n + 1)
    dp[0] = True
    for i in range(1, n + 1):
        for j in range(i, -1, -1):
            substr = s[j: i]
            if substr in wordDict and dp[j]:
                dp[i] = True

    return dp[n]


def wordBreak_opt(s: str, wordDict: list[str]) -> bool:
    n = len(s)
    dp = [False] * (n + 1)
    dp[0] = True
    # dp[i]表示长度到i是否可行,dp[0]表示长度为0可行
    for i in range(1, n):  # i范围:[1，n-1]
        for j in range(i + 1, n + 1):  # j范围:[i+1,n]
            if (dp[i] and (s[i:j] in wordDict)):
                dp[j] = True
    return dp[n]


if __name__ == '__main__':
    print(wordBreak("leetcode", ["leet", "code"]))  # True
    print(wordBreak(s="applepenapple", wordDict=["apple", "pen"]))  # True
    print(wordBreak(s="catsandog", wordDict=["cats", "dog", "sand", "and", "cat"]))  # False
